home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / OTPOLY.ZIP / polygon.doc < prev    next >
Text File  |  1996-08-07  |  9KB  |  264 lines
  1.  
  2.                      - THE OUTLAW TRIAD DEMO-SERIES -
  3.  
  4. ───────────────────────────────■ PART IX ■────────────────────────────────────
  5.  
  6.                          Written by : Inopia/OT
  7.                          Code in    : Pascal
  8.                          Topic      : Polygons
  9.  
  10. ──────────────────────────────■ Introduction ■────────────────────────────────
  11.  
  12.  Welcome to the Outlaw Triad demo-series! In these series we will be talking
  13.  about programming demo-effects in either pascal or assembler. Theory behind
  14.  the effects shall be discussed while a full sourcecode is also provided.
  15.  This time we discuss polygons. The way I'm going to describe is not the only
  16.  one. But who cares, the only difference between this and other routines, is
  17.  that some scan over the X-axis, instead of the Y-axis as we do. You can use
  18.  polygons to create filled 3d objects, like seen in many demos. And when you
  19.  understand these basics, you can expand the code to texture mapping, gourad
  20.  shading and a lot more! Ok, let's get started with some serious explaining.
  21.  
  22. ─────────────────────────────────■ Theory ■───────────────────────────────────
  23.  
  24.  We will discuss how to draw filled triangles. Hmm, you may find yourself
  25.  wondering, why the hell triangles? If not, skip this. Otherwise, triangles
  26.  have some very special abilities. First of all, any other geometrical shape
  27.  can be formed with multiple triangles. A square can be represented by two
  28.  triangles for example (just like those stupid tangram puzzles). And second,
  29.  in a triangle, step values are the same everywhere. You will see this later
  30.  on (if you get that far anyhow, cos I'm not very good at this stuff :-) ).
  31.  Furthermore, it's pretty standard! When your 3d engine is up to multiple
  32.  faced objects, you can load in 3DS files as they work with triangles too.
  33.  
  34.  THE BASICS
  35.  ----------
  36.  
  37.  A polygon can be drawn on a (virtual) screen by drawing horizontal lines.
  38.  
  39.              -
  40.             ---
  41.            -----
  42.           -------
  43.          ---------
  44.         -----------
  45.        ----------
  46.       --------
  47.      ------
  48.     ----
  49.    --
  50.   -
  51.  
  52.  Yeah well, it doesn't really look like a poly, but hey, it's textmode... :-)
  53.  Anyhow, we will need to sort the coordinates on Y values. The coordinates
  54.  are called P1, P2, and P3. They are 2D coordinates and can be referred to
  55.  as P1.X,P1.Y,P2.X,P2.Y etc..
  56.  
  57.             P1
  58.            / \
  59.           /   \
  60.          /     \
  61.         /       \
  62.        /         \
  63.       /        /  P3
  64.      /      /
  65.     /    /
  66.    /  /
  67.   //
  68.  P2
  69.  
  70.  So, we should sort this stuff on Y-values. It's needed to find the longest
  71.  side and all that, so it's really crucial. Pay attention. There are only
  72.  3 coordinates, so the sorting is simple (another reason to use triangles!).
  73.  We are going to put P1, P2, and P3 into TOP, MID, and BOT which are 2d points
  74.  too.
  75.  
  76.  -Find out wich of P1.Y and P2.Y is the smallest (remember, we are looking
  77.   for coordinates who are high on the screen, so with low Y-values..), and
  78.   put that one in TOP. The other on in BOT.
  79.  -Now find out where to put the P3. There are three possibilities:
  80.    -P3.Y>TOP.Y and P3.Y<BOT.Y. This means you can put it in between: MID=P3.
  81.    -P3.Y<TOP.Y. It's the smallest! Since TOP isn't anymore, you put it in MID.
  82.     TOP=MID. Now put the P3 in top. TOP=P3.
  83.    -P3.Y>BOT.Y. It's the biggest, so you can safely store it in BOT. But put
  84.     BOT in MID first: MID=BOT. BOT=P3
  85.  
  86.  Well, this sorting routine should be about the largest part of your routine,
  87.  since a flat poly involves nothing more than a bit of interpolating.
  88.  
  89.  INTERPOLATING?
  90.  --------------
  91.  
  92.  Interpolating is a way of getting from A to B in C steps.
  93.  
  94.    A------------------B
  95.  
  96.   10km               50km
  97.  
  98.  Just like those neat math books you had years ago. Well, town A is 10km,
  99.  and city B is 50km. So they're 40km apart. But you're in town A, and your
  100.  girlfriend is in city B. So you want to get over there PRONTO! You don't
  101.  want to spend more time sitting in your rusty old car than about 25 minutes.
  102.  So C=25.
  103.  
  104.   Delta=(B-A)/C
  105.  
  106.  Delta, also called stepvalue, is the distance in km you should travel every
  107.  minute to get to your girlfriend in time. Delta is the greek letter EB.
  108.  
  109.   EB=(50-10)/25
  110.   EB=40/25
  111.   EB=1.6
  112.  
  113.  So you should travel 1.6km every minute to get there in time. That's
  114.  
  115.   1.6*60=96km/hr
  116.  
  117.  But your rusty little car gets a flat tire and you don't make it... <hehe>
  118.  What did we learn here? Well, we can now interpolate! We can get from one
  119.  X-value to another one in any amount of steps, like from the TOP.X to the
  120.  MID.X. This is quite important.
  121.  
  122.  BACK TO THE BASICS
  123.  ------------------
  124.  
  125.  Ok. Let's grab the triangle again..
  126.  
  127.             TOP
  128.            / \
  129.           /   \
  130.          /     \
  131.         /       \
  132.        /         \
  133.       /        /  MID
  134.      /      /
  135.     /    /
  136.    /  /
  137.   //
  138.  BOT
  139.  
  140.  
  141.  As you can see, there's one long side (TOP-BOT), and two shorter ones
  142.  (TOP-MID), and (MID-BOT). Now we are going to make two loops by cutting
  143.  the long side in two:
  144.  
  145.             TOP           -
  146.            / \             |
  147.           /   \            | Loop1
  148.          /     \           |
  149.         /       \          |
  150.        /         \         |
  151.      Q*        /  MID     -
  152.      /      /              |
  153.     /    /                 | Loop2
  154.    /  /                    |
  155.   //                       |
  156.  BOT                      -
  157.  
  158.  We have inserted point Q in here just to clearify things, you really don't
  159.  need to know it's coordinates (you can find out if you would want to).
  160.  With the stuff we've just learned, we can start interpolating the X-values
  161.  needed for the horizontal lines. Make a loop from TOP.Y to MID.Y.
  162.  This is LOOP1:
  163.  
  164.   FOR NR=TOP.Y TO MID.Y DO
  165.   NEXT NR
  166.  
  167.  Now we must start to interpolate. Firstly we get two EB (Delta, (B-A)/C)
  168.  values, we shall graciously call EBR and EBL. EBLeft and EBRight. The
  169.  first one we do is TOP-MID:
  170.  
  171.   EBL=(MID.X-TOP.X)/(MID.Y-TOP.Y)
  172.  
  173.  This makes perfect sense, just check out the "picture". We have to "travel"
  174.  from TOP.X to MID.X. The distance (C) is from TOP.Y to MID.Y. So, MID.Y-TOP.Y!
  175.  The other one is (TOP-Q). But we don't know QX! Well, Q is on (TOP-BOT), so
  176.  we can use BOT in stead of Q:
  177.  
  178.   EBR=(BOT.X-TOP.X)/(BOT.Y-TOP.Y)
  179.  
  180.  Now we can start interpolating:
  181.  
  182.   RPOS=TOP.X
  183.   LPOS=TOP.X
  184.   FOR NR=TOP.Y TO MID.Y DO
  185.     HLINE(RPOS,LPOS,NR,COLOR)
  186.     RPOS=RPOS+EBR
  187.     LPOS=LPOS+EBL
  188.   NEXT NR
  189.  
  190.  HLINE is ofcourse the routine wich draws the horizontal lines. COLOR is the
  191.  color the poly should become, hence the name. Now we have drawn half the
  192.  poly. That's not enough for real coders like you, so we shall get on with
  193.  the second part. This is ofcourse the same routine, with other values. We
  194.  must now interpolate (MID-BOT), and (Q-BOT). Since Q-BOT is the same side
  195.  as TOP-BOT, we can still use the EBR, calculated before. But EBL has to be
  196.  recalculated.
  197.  
  198.   EBL=(BOT.X-MID.X)/(BOT.Y-MID.Y)
  199.  
  200.   And now we go and draw the second part of the triangle like this:
  201.  
  202.   LPOS=MID.X
  203.   FOR NR=MID.Y+1 TO BOT.Y DO
  204.     HLINE(RPOS,LPOS,NR,COLOR)
  205.     RPOS=RPOS+EBR
  206.     LPOS=LPOS+EBL
  207.   NEXT NR
  208.  
  209.  RPOS shouldn't be changed, for the previous loop should have left it exactly
  210.  at QX. Also, since your loops are TOP.Y-MID.Y and MID.Y-BOT.Y, you're doing
  211.  MID.Y twice. So that's why the second loop should start at MIDY+1.
  212.  
  213.  HORIZONTAL LINES
  214.  ----------------
  215.  
  216.  Yeah well, this should be quite obvious. Just plot a row of pixels:
  217.  
  218.   FOR I=X1 TO X2 DO
  219.     PUTPIXEL(I,Yline,Color)
  220.   NEXT I
  221.  
  222.  Convert this to a fast inline assembler routine to gain speed. Shouldn't
  223.  be too hard if you know assembler.
  224.  
  225.  Ok, I believe this is about all. You should be able to create flatpolys now.
  226.  If I'm up to it, I'll release a sequal, explaining how to upgrade these
  227.  flatpolys to gouraud and texture, and eventually PHONG, but I'm too tired
  228.  right now. You can always contact me for futher talk.
  229.  
  230.    Later,
  231.  
  232.        -Inopia/Outlaw Triad-
  233.  
  234. ───────────────────────────────■ Distro Sites ■───────────────────────────────
  235.  
  236.  Call our distribution sites! All our releases are available at:
  237.  
  238.   BlueNose      World HQ          +31 (0)345-619401
  239.   The Force     Distrosite        +31 (0)36-5346967
  240.   Bugs'R'Us     Distrosite        +31 (0)252-686092    More distros wanted!
  241.   The 7 Angels  Distrosite        +31 (0)715-148377    (preferably outside
  242.   ShockWave     South African HQ  +27 (011)888-6345     of the Netherlands)
  243.   Society HQ    United States HQ  +1  (518)465-6721
  244.   ACe World     Brazilian HQ      +55 21-259-8847
  245.  
  246.  Also check the major FTP/WWW sites for Outlaw Triad productions.
  247.  
  248. ──────────────────────────────────■ Contact ■─────────────────────────────────
  249.  
  250.  Want to contact Outlaw Triad for some reason? You can reach us at our
  251.  distrosites in Holland. Or if you have e-mail access, mail us:
  252.  
  253.    Vulture   (coder/pr)   comma400@tem.nhl.nl
  254.    Inopia    (coder)      inopia@horizon.nl
  255.  
  256.  Our internet homepage:
  257.  
  258.    http://www.tem.nhl.nl/~comma400/vulture.html
  259.  
  260.  These internet adresses should be valid at least till june 1997.
  261.  
  262. ──────────────────────────────────────────────────────────────────────────────
  263.  
  264.                Quote: Welcome to the future! She just started!